package com.cty._04_Optimization._41_StreamMedian;

/**
 * @Auther: cty
 * @Date: 2020/7/16 15:30
 * @Description: 面试题41：数据流中的中位数
 * 题目：如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么
 * 中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，
 * 那么中位数就是所有数值排序之后中间两个数的平均值。
 *
 * 最大堆最小堆实现
 * 时间复杂度：
 *      每次插入平均  O(logN)
 *      获取中位数  O(1)
 *      总计  N*O(logN) + O(1)
 * 空间复杂度：O(N)
 * @version: 1.0
 */
public class StreamMedian {
    private MaxHeap maxHeap;
    private MinHeap minHeap;

    public StreamMedian(){
        int maxSize = 100;
        maxHeap = new MaxHeap(maxSize);
        minHeap = new MinHeap(maxSize);
    }

    public void insert(int key){
        DataItem current = new DataItem(key);
        int size = minHeap.size() + maxHeap.size();

        if((size & 1) == 0){  // i为偶数则向最小堆插入数据
            if(!maxHeap.isEmpty() && current.getKey() < maxHeap.findMax().getKey()){  // 若当前数字小于最大堆的部分数字
                maxHeap.insert(current);
                current = maxHeap.remove();
            }
            minHeap.insert(current);
        }else{  // i为奇数则向最大堆插入数据
            if(!minHeap.isEmpty() && current.getKey() > minHeap.findMin().getKey()){
                minHeap.insert(current);
                current = minHeap.remove();
            }
            maxHeap.insert(current);
        }  // end else
    }  // end insert()

    public double getMedian() throws Exception {
        int size = minHeap.size() + maxHeap.size();
        if(size == 0)
            throw new Exception("No numbers are available");

        if((size & 1) == 0)
            return (maxHeap.findMax().getKey() + minHeap.findMin().getKey())*0.5;
        else
            return minHeap.findMin().getKey();
    }  // end getMedian()

}  // end class
